package Algorithm.Dp;

import java.util.*;

public class Leetcode1027_最长等差数列 {
    class Solution {
        public int longestArithSeqLength(int[] nums) {
            int n = nums.length;
            Map<Integer, List<Integer>> map = new HashMap();
            for(int i = 0; i < nums.length; i++){
                List<Integer> list = map.computeIfAbsent(nums[i], k->new ArrayList<Integer>());
                list.add(i);
            }

            int[][] dp = new int[nums.length][nums.length];
            for (int i = 0; i < nums.length; i++) {
                Arrays.fill(dp[i], 2);
            }
            int max = 0;
            for(int k = 0; k < nums.length; k++){
                for(int i = 0; i < k; i++){
                    List<Integer> index = map.getOrDefault(nums[i] - (nums[k] - nums[i]), null);
                    int count = 2;
                    if(index!=null){

                        for(int j : index){
                            if(j < i){
                                count = Math.max(dp[j][i]+1, count);
                            }
                        }
                    }
                    dp[i][k] = count;
                    max = Math.max(count, max);
                }
            }

            return max <= 2 ? 2 : max;
        }
    }
}
